class Solution(object):
    def copyRandomBinaryTree(self, root):
        d = {}
        def search(node):
            if not node:
                return None
            if node in d:
                new_node = d[node]
            else:
                new_node = NodeCopy(node.val)
                d[node] = new_node
            if node.random:
                random_node = node.random
                if random_node in d:
                    new_random_node = d[random_node]
                else:
                    new_random_node = NodeCopy(random_node.val)
                    d[random_node] = new_random_node
                new_node.random = new_random_node
            new_node.left = search(node.left)
            new_node.right = search(node.right)
            return new_node

        return search(root)
